/**
 * 第 i 个包裹的重量为 weights[i]。
 * 按weights的顺序装载包裹。返回能在D天内将所有包裹送达的最低运载能力
 * @param {number[]} weights
 * @param {number} days
 * 暴力法：逐个测试最低运载能力，从平均数 sum(weights)/days 开始测
 * 一行代码实现数组求和：eval(array.join("+"))
 */
var shipWithinDays = function (weights, days) {
  // 初始化最低运载能力
  let re = Math.max(
    Math.ceil(eval(weights.join("+")) / days),
    Math.max(...weights)
  );

  while (true) {
    let i = 0,
      currWeight = 0,
      day = 1;

    // 遍历所有货物
    while (i < weights.length) {
      if (currWeight + weights[i] <= re) {
        // 小于当前设定的最低运载能力则加入
        currWeight += weights[i];
        i++;
      } else {
        // 否则直接进入下一天
        day++;
        currWeight = 0;
      }
    }

    // 如果测出来的day比要求的天数days小，说明得到了结果
    if (day <= days) {
      return re;
    }

    // 否则就提升最低运载能力
    re++;
  }
};

// 二分法
var shipWithinDays2 = function (weights, days) {
  let left = Math.max(
    Math.ceil(eval(weights.join("+")) / days),
    Math.max(...weights)
  ),
    // right定义为weights数组求和
    right = eval(weights.join("+"));

  while (left < right) {
    let mid = left + Math.floor((right - left) / 2),
      i = 0,
      currWeight = 0,
      day = 1;

    while (i < weights.length) {
      if (currWeight + weights[i] <= mid) {
        currWeight += weights[i];
        i++;
      } else {
        day++;
        currWeight = 0;
      }
    }

    if (day <= days) {
      // 运载力有剩则降低
      right = mid;
    } else {
      // 运载力不够则提升
      left = mid + 1;
    }
  }

  return left;
};
